\documentclass[a4paper]{article}
\usepackage[UTF8]{ctex}
\usepackage{listings}
\lstset{numbers=left,
	basicstyle=\ttfamily,
	language=c++}

	\title{作业一: 双链表的设计和实现}

	\author{韩李玮\\ 统计学 3210104658}

	\date{\today}

\begin{document}
	
	\maketitle

\section{创建要求}
			
设计DoubleLinkedList<DT>模板类时应注意包含一个链表应具备的所有基本功能，如insert，erase等函数，同时要注意防止内存泄漏。

\section{设计思路}
1.进行头文件编写。\par
2.首先明确结构，需要设计哪些类的实现，如const\_iterator类，iterator类，并将类用友元联系起来。\par
3.明确每个类需要实现哪些函数，如DoubleLinkedList<DT>类需要实现push\_back,push\_front等一系列函数，对于一些自定义的类型，进行运算符重载。\par
4.明确每个类自身需要什么成员完成函数实现，如DoubleLinkedList<DT>类需要theSize，head，tail等成员。\par
5.进行测试程序编写。\par
6.首先编写外部函数find。\par
7.最后编写main函数对头文件进行测试。\par

\section{在书本基础上添加的函数}
1.const\_iterator类对$--$运算符的重载
\begin{lstlisting}
	const_iterator & operator-- ( )
	{
		current = current->prev;
		return *this;
	}
	
	const_iterator operator-- ( int )
	{
		const_iterator old = *this;
		--( *this );
		return old;
	}
\end{lstlisting}
2.iterator类对$--$运算符的重载
\begin{lstlisting}
	iterator & operator-- ( )
	{
		this->current = this->current->prev;
		return *this;
	}

	iterator operator-- ( int )
	{
		iterator old = *this;
		--( *this );
		return old;
	}
\end{lstlisting}
3.printList函数
\begin{lstlisting}
	void printList( ) 
	{
		iterator p{head->next};
		while( p.current->next )
		{
			std::cout << *p << ' ' ;
			p++;
		}
		std::cout << std::endl;
	}
\end{lstlisting}
4.find函数（外部函数）
\begin{lstlisting}
	template <typename DT>
	typename DoubleLinkedList<DT>::iterator find 
		(DoubleLinkedList<DT> & _list,const DT & _val)
	{
		typename DoubleLinkedList<DT>::iterator p =
						_list.begin();
		typename DoubleLinkedList<DT>::iterator q;
		int i = 1;
		for (p = _list.begin(); *p != _val; ++p)
		{
			if (i == _list.size())
			{
				std::cout << "Not found." << std::endl;
				return q;
			}
			i++;
		}
		std::cout << "Found at the " << i <<
			 " position of the list" << std::endl;
		return p;
	}
\end{lstlisting}
5.main函数
\begin{lstlisting}
	int main()
	{
		DoubleLinkedList<int> L;
		DoubleLinkedList<int>::iterator iter;
		for(int i = 1; i <= 5; i++)
		{
			L.push_back(i);
		}
		L.printList();
		iter = find(L,3);
		L.erase(iter);
		L.printList();
		iter = find(L,3);
		return 0;
	}
\end{lstlisting}
\section{测试结果及内存泄漏检查}

测试结果：\\
1 2 3 4 5 \\
Found at the 3 position of the list \\
1 2 4 5 \\
Not found.\\

内存泄漏检查：\\
==192639== \\
==192639== HEAP SUMMARY: \\
==192639==     in use at exit: 0 bytes in 0 blocks \\
==192639==   total heap usage: 9 allocs, 9 frees, 73,896 bytes allocated \\
==192639== \\
==192639== All heap blocks were freed -- no leaks are possible \\
==192639== \\
==192639== For lists of detected and suppressed errors, rerun with: -s \\
==192639== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) \\

由检查知，没有内存泄漏。\\

\section{关于find和erase的一些思考与改进}
在测试程序的时候，我发现find一个不存在的值返回的空指针在erase时会出现问题，所以打算对erase函数进行一系列修改。同时无论是对于传入一个迭代器还是两个迭代器的erase函数，如果多次删除同一个迭代器，将会出现极大的问题。\par
因此在测试时为保证程序正常执行，可以编写一个返回bool值的外部函数，判断iterator是否指向正确的位置，通过该bool型函数控制erase函数是否执行。\par
但我可以将代码写在此处：
\begin{lstlisting}
	Class DoubleLinkedList<DT>
	{
		public:
		bool canerase (iterator & itr)
		{
			if( itr.current && 
			itr.current->prev && 
			itr.current->next)
			return true;
			else
			return false;
		}	
	}
\end{lstlisting}
同时将erase函数更新为
\begin{lstlisting}
	iterator erase( iterator itr )
	{
		iterator q;
		if (canerase(itr))
		{    
			Node *p = itr.current;
			iterator retVal{ p->next };
			p->prev->next = p->next;
			p->next->prev = p->prev;
			p->prev = nullptr;
			p->next = nullptr;
			delete p;
			theSize--;
			return retVal;
		}
		else
		{
			std::cout << "Can't erase." << std::endl;
			return q;
		} 
	}
\end{lstlisting}
和\\	
\begin{lstlisting}
	iterator erase( iterator from, iterator to )
	{
		iterator itr = from;
		iterator q;
		for(itr = from; itr != to && canerase(itr);)
		itr = erase( itr );
		if(itr == to)
			return to;
		else
		{
			std::cout <<"Can't erase." << std::endl;
			return q;
		}
	}
\end{lstlisting}
可以解决erase时出错的情况。

\section{小结}
以上就是我在完成这次作业时的思考。制作双链表的过程对我理解的迭代器的功能和尝试使用迭代器带来了很大的帮助。
\end{document}

